1. Field of the Invention
This invention relates to the field of computer software, and, more specifically, to transaction processing and object or resource locking.
Portions of the disclosure of this patent document contain material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office file or records, but otherwise reserves all copyright rights whatsoever. Sun, Sun Microsystems, the Sun logo, Solaris, Java, JavaOS, JavaStation, HotJava Views and all Java-based trademarks and logos are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries.
2. Background Art
In modern computing environments, it is commonplace to store and access a variety of diverse information and data. To efficiently utilize the information, the information is stored in a database and is structured in a manner that provides a user with the ability to interpret and manipulate the information (referred to as a xe2x80x9cdata structurexe2x80x9d). One type of database structure is in the form of a table, where each row of the table contains a record and each column specifies a field in the record. For example, a table can be used to store information regarding a company""s inventory where each record is a specific item in the inventory and each field specifies information about the item (e.g., the name of the product, the price of the product, etc.). Data structures may vary depending on the application and type of database utilized. As a result of the diverse types of information being utilized (e.g., text, images, sound, video, etc.), data structures have grown increasingly complex.
Each time a computer system performs an activity, the activity is referred to as a transaction. For example, when a customer order is entered, or an inventory item is updated, a transaction for each activity is executed by the computer system. Thus, when information in a data structure is accessed or manipulated, a transaction is executed by the computer system. A transaction may need access to a record in a database or a portion of information in a database. Alternatively, a transaction may modify the entire database. When executing transactions, a computer system may execute a group of transactions at one time (referred to as batch processing), or may execute each transaction immediately after the transaction is received by the system (referred to as transaction processing). Transactions contain certain properties that must be adhered to. For example, transactions must be isolated such that each transaction must be contained separately from each other transaction. Additionally, transactions must provide for recoverability (the ability to establish a previous or new status from which execution can be resumed in the event of a system or execution failure). Required transaction properties are also referred to as low level details of a transaction.
In many modern applications, increasingly complex data structures coupled with transaction processing capabilities is becoming a common requirement. The complexity of these applications, in terms of the data structures, algorithms, and type of the transactions used, does not fit well in the framework offered by traditional database systems. Persistent programming languages (PPL) (programming languages that provide for data to have a lifetime that persists for a specified amount of time) that support transaction processing may be utilized by programmers as an alternative or in combination with traditional database systems. To provide adequate support, some PPLs automatically enforce required transaction properties. Thus, low level transaction details (e.g., enforcing a transaction""s properties) are automatically performed without input from a programmer.
One automated low level detail consists of the acquisition and release of a lock. A lock is a mechanism that restricts use of a resource to the holder of the lock. By locking a resource, the integrity of the data in the resource is ensured by preventing more than one user (or transaction) from accessing or changing the same data or object at the same time. Locking is a popular technique to implement concurrency control for a transaction processing system. Programming systems that tightly couple a transaction processing engine with a high-level programming language usually include in their runtime a component that automates the requesting of locks on behalf of executing programs. Such automation of locking guarantees that transactions are well formed (i.e., that the transaction holds the lock of a data item in the correct mode prior to executing an operation on that data item). Relational, object-oriented, and object-relational database systems as well as persistent and database programming languages have recourse to such locking automation, both to simplify the programmer""s work and to avoid depending on the programmer to always formulate well formed transactions. There are several types of locks that may be used.
One type of lock is a shared lock. A shared lock permits multiple transactions to read (view) an item simultaneously without any modification or addition to the item (no writing is permitted). A shared lock is referred to as permitting concurrent (or concurrency) control by a transaction (i.e., multiple transactions are permitted to concurrently access a resource). Another type of lock is an exclusive lock. An exclusive lock permits one transaction to read and write to an item while excluding all other transactions from reading or writing to the item.
The locking and unlocking of resources must be administered to ensure that any required lock properties are complied with. For example, two or more different transactions cannot each acquire an exclusive lock at the same time for the same resource. Additionally, locks must be administered to provide a queue for transactions that are waiting to acquire a lock, and to rollback any executed actions if a deadlock results (i.e., when each of two transactions are waiting for a lock release from the other before continuing). For example, a deadlock occurs if transaction 1 has a lock on resource A and is waiting to acquire a lock on resource B, and transaction 2 has a lock on resource B and is waiting to acquire a lock on resource A.
A locking protocol partially determines the administration of a locking and unlocking of resources. A locking protocol determines how and when a transaction is granted (or acquires) a lock for a resource and when the resource is unlocked (i.e., the lock is released allowing other transactions to acquire a lock on that resource). A lock manager administers a locking protocol.
For example, in a two-phase locking protocol, each transaction issues a lock and unlock request in two phases. In one phase, referred to as the growing phase, a transaction may obtain locks but may not release any lock. In the second phase, referred to as the shrinking phase, a transaction may release locks but may not obtain any new locks.
Another protocol, referred to as a graph-based protocol, a partial ordering of information in a database is performed. For example, a set R of resources consisting of R1, R2, R3, . . . , Rh is ordered such that Rixe2x86x92Rj. In this manner, any transaction accessing both Ri and Rj must access Ri before accessing Rj. With this ordering, the set R may be viewed as a directed acyclic graph, called a database or resource graph. A directed graph may be viewed as the tree of FIG. 2, where each node of the tree is a resource. Each resource descends from another resource (referred to as a parent resource) up to the root of the tree that has no parents (resource A 200). In a graph-based protocol, the following rules are followed: (1) the first lock by a transaction T may be on any data item, (2) subsequently, a data item or resource R can be locked by T only if the parent of R is currently locked by T, (3) resources can be unlocked at any time, and (4) a resource that has been locked and unlocked by T cannot subsequently be relocked by T. For example, referring to FIG. 2, if T needs access to resource C 204, both resource C 204 and resource A 200 must be locked. Similarly, if T needs access to resource J 218, in addition to locking resource J 218, all of the parents of resource J 218 must be locked (i.e., resources H 214, D 208, B 202, and A 200). Thus, in some cases, a transaction must lock resources that it does not access (i.e., the parent resources of a resource being accessed).
FIG. 3 demonstrates an example of lock acquisition according to a traditional protocol. In the traditional protocol, each resource is allocated a lock data structure. This lock data structure is updated every time a lock operation changes the state of the resource""s lock. FIG. 3 demonstrates a scenario where two resources, O1 300 and O2 302, have been read by a transaction T1, and O2 302 is about to be read by transaction T2. The state of the lock of each resource is shown before (304-306) and after (308-310) the acquisition of the lock on O2 302 by T2. When transaction T2 requests the lock on resource O2 302 in read mode, the lock data structure associated with O2 302 is updated to reflect the new lock state (i.e., lock owned by T1 and T2 in read mode).
Each of the lockable resources may be a record in a database, a field of a record, an entire database, or in an object oriented system (discussed in detail below) a single object, for example. The size or level of the lockable resource is referred to as the granularity of the resource (e.g., the field level v. the record level v. the table level).
A lock is comprised of a data structure that records the identity of the transactions that are given the right to execute operations on the resource the lock protects. Each time a lock is acquired, memory is used for the lock data structure. The memory utilized by the lock remains unavailable until released through garbage collection or some other method. Consequently, one goal in lock administration is to minimize the memory locks consume, which usually translates in minimizing the number of locks.
The process of creating and manipulating a lock is time consuming. Thus, another goal in lock processing is to minimize the lock processing cost for acquiring and releasing a lock.
As resource granularity becomes finer, more resources are available for transactions. Such resource availability occurs because locks are placed on smaller resource units, freeing remaining resources that may be locked if the resource is coarser. Consequently, another objective in lock processing is to utilize a fine resource granularity.
Locking may be performed manually by programmers who then explicitly put lock requests in their programs, or automatically at runtime without input from programmers. When applied in the context of general purpose programming languages, both solutions may result in many unnecessary redundant lock requests (i.e., a lock request for a lock already owned) because of the complex data structures and algorithms these programming languages enable. Consequently, one goal of lock management is to minimize the processing time spent to process redundant lock requests.
The objective of a lock management implementation is to obtain the best combination of low memory consumption, low processing costs, and fine granularity of locking.
When the programming interface is a rich programming language (e.g., the Java(trademark) programming language), a problem that is encountered is that locking automation can result in an overwhelming number of generated lock requests. However, each lock request that is issued is not always necessary. Lock requests that, for example, target an immutable data item or an object created by the lock requester may not be necessary. The term object may refer to any data item. Objects created by the lock requester are typically out of reach of other transactions until the requester commits and are therefore not always necessary (if ACID transactions are used). In other instances, the requester already holds a lock in a mode equivalent or stronger on the requested data item and thus another lock request is unnecessary. A problem encountered by current locking systems is that in many instances these unnecessary requests are issued and thereby result in additional processing overhead. When automated locking system is interfaced with a lock manager that uses lock-value sharing with memoization, the problem becomes increasingly complex. Memoization is an algorithmic technique that saves (memoizes) a computed answer for later reuse, rather than recomputing the answer. The computed answer is typically saved in cache memory so that it can be quickly accessed. A memorized function remembers the arguments to which it has been applied together with the resulting computation. If the function is re-applied to the same argument, the function returns the cached answer rather than repeating the computation. Memoization can be used in conjunction with a lock manager that uses shared lock states to avoid calls to the lock manager, and thus, speed up the processing of lock request. Below is some pseudo code to show how memoization works in the context of a lock manager that use lock state sharing. The memoization cache in this particular example consists of a single line per type of request (e.g., request for a read lock, request for a write lock, etc.).
Practical implementation of this pseudo-code takes from 4 to 8 assembler instructions, depending on what is already cached in machine registers. The sequence of instructions that performs the memoization of a lock manager operation is typically inlined in the application code. Two phenomenon currently limit the effectiveness of the memoization cache of a transaction:
1. the frequent interleaving of accesses to objects pre-existing the transaction and objects created by the transactions.
2. the frequent interleaving of accesses to mutable and immutable object (e.g., instance of java.lang.String in the Java(trademark) programming language)
When automated locking system is interfaced with a lock manager that uses lock-value sharing with memoization unnecessary lock requests significantly decrease the efficiency of the memoization cache and results in a dramatic performance loss. Thus there is a need for a method to improve the efficiency of memoized lock operations in order to increase the performance of automated locking systems. More particularly there is a need for a system that improves the performance of automated locking systems that are interfaced with a lock manager that utilizes lock-value sharing with memoization.
Lock requests directed at immutable and new objects may be unnecessary. One simple way to filter such lock requests is to tag such object as immutable, and test this tag prior to process a lock request for such objects. To avoid adding space to the object representation, the tag can be stored in place of the lock pointer of the object. A similar technique can be used for objects created by the current transaction. Lock request directed as either an immutable or a new object can then be filtered by testing the value of the lock pointer against either an xe2x80x9cimmutable objectxe2x80x9d tag, or the xe2x80x9ccreated objectxe2x80x9d tag of the transaction that performs the test, prior to processing a lock request. A problem with this solution is that it increases the pathlength of lock request with two additional tests and a branch. Thus, there is also a need for a system that more efficiently filters lock requests directed at immutable and/or objects allocated by transactions.
The present invention provides for low space-overhead locking for transaction processing systems by sharing lock states. Each resource or object has an associated lock state. A lock state is comprised of a set of transactions that own a lock in a specific mode. Among other modes, a locking mode may comprise a read mode or a write mode.
Resources may share the same lock state if the state of their respective lock is equal. During its lifetime, a resource may be associated with various lock states, each lock state being the representation of the lock of that resource at a given time. Locking operations change the association between a resource and a lock state, should such a change be necessary.
In one embodiment of the invention, a table of immutable lock states (TILS) records all of the immutable lock states that were created by lock operations in order to avoid duplication of lock states with equal value. Locking operations (e.g., acquire, release) that yield new lock state values must consult the TILS to retrieve the corresponding immutable lock state.
To acquire a lock on a resource R, after ensuring that there is no conflicts, the value of a new lock state is computed by adding the current transaction to the lock state currently associated with R. The computed lock state value is used to retrieve an immutable lock state from the TILS (if no such lock state exists, a new one is registered to the TILS and is returned). The lock acquisition completes by updating the association of the resource to the new lock states returned by the TILS.
To release a lock for a specific resource, the transaction determines the lock state value that will result after removing itself from the lock state for that resource. The computed lock state value is used to retrieve an immutable lock state from the TILS (if no such lock state exists, a new one is registered to the TILS and is returned). The lock release completes by updating the association of the resource to the new lock states returned by the TILS.
As described, all lock operations perform transitions of lock states that are both deterministic and independent of the locked resource. If a locking operation for a transaction T on a lock state S1 yields a state S2, it will always do so, independently of the resource the operation applies to. For instance, acquiring a read lock for a transaction T1 on a resource R associated with a lock state consisting of a read owner set that contains T2 will always yield a lock state made of a lock owner set that contains T2 and T1, whatever the resource R is. In one embodiment of the invention, lock state transitions (e.g., acquire (T1, Read): Owner(Read)={T2}ØOwner(Read)={T2,T1}) are cached to avoid both computation of lock states and look up in the TILS. Each transaction maintains one lock state transition cache per locking operation.
When a transaction has completed execution, all resources associated with the transaction must be released. In one embodiment, the transaction maintains a lock set that maintains information regarding each resource for which it has obtained a lock. The transaction then releases each resource in the lock set as described above. In one embodiment, the lock set is implemented in a stack where each reference is pushed onto the stack when the lock is acquired and popped when the lock is released. In another embodiment, lock sets are not maintained and the TILS is scanned upon transaction completion to determine which lock states contained the transaction as an owner.
A problem encountered by the automated locking systems described above is that such systems are often required to process unnecessary lock requests. These unnecessary lock requests add processing overhead and therefore slow down the system. An embodiment of the invention provides a way to reduce the volume of unnecessary lock requests and thereby increase the efficiency of the system. The volume of unnecessary lock requests is reduced in accordance with one embodiment of the invention, by filtering unnecessary lock requests at runtime. The filtering process allows the system to avoid the processing overhead required to process a lock request at the lock manager when such processing is not necessary. Thus, an embodiment of the invention defers processing by the lock manager unless such processing is required.